//
//判断链表(带头节点)是否有环(简单环,不讨论环来环去的，就讨论尾节点指向了该链表中的某一个节点即可)
//环的定义:尾节点连接了任意一个该链表的节点
//相关变量和数据结构(李存葆)第五版保持一致 方便复习与最后老师阅卷
// Created by Arc on 2024/4/28.
//

//链表所有节点数量(不含头节点)
#define LinkListNodeNum 10
//定义环的位置
#define HuanPos 7

#include <iostream>

#include <vector>

using namespace std;

//参数化、配置化
typedef int ElementType;


/**
 * 链表节点定义
 */
typedef struct LinkNode {
    ElementType data;
    LinkNode *next;
} LinkNode;


/**
 * 初始化该线性表、创建头节点、赋初试测试值
 */
void initAndCreateListAndSetData(LinkNode *&L) {
    LinkNode *tail; //定义尾指针
    //分配内存空间 该空间作为该单链表的头节点 且此时该单链表只有该头节点 所以该指针指向的也是该整个链表的地址
    L = (LinkNode *) malloc(sizeof(LinkNode));
    tail = L; //一开始 尾指针指向头节点
    for (int i = 0; i < LinkListNodeNum; i++) {
        //给每个节点数据域 赋测试值  不重要
        LinkNode *oneNode = (LinkNode *) malloc(sizeof(LinkNode));
        oneNode->data = i * 10;
        tail->next = oneNode; //尾插法体现在这里
        tail = oneNode; //尾指针 永远指向该链表最后一个节点
    }
    //for循环结束 最后一个节点的next域值指向null
    tail->next = NULL;
}


/**
 * 根据位序找到并返回对应节点的指针(算法就是返回对应位序元素的前一个节点的next值)
 * @param L
 * @param wx
 * @return
 */
LinkNode *locateElementByWx(LinkNode *L, int wx) {
    LinkNode *p = L;
    LinkNode *result;
    if (p == NULL || p->next == NULL) {
        cout << "该链表不存在或者该链表只有头节点,不合法!" << endl;
        return NULL;
    }
    if (wx < 1) {
        cout << "期待的位序不合法!" << endl;
        return NULL;
    }
    int j = 1;
    while (j < wx - 1 && p != NULL) {
        p = p->next;
        j++;
    }
    if (p == NULL) {
        return NULL;
    } else {
        //指针p即为所有为序的节点的前一个节点
        result = p;
    }
}

/**
 * 针对没有环的单链表 造一个环(此处是把尾节点的next指针指向正数位序为tailNext的节点上(不含头节点，首节点为序为1))
 */
void createHuan(LinkNode *&L, int wx) {
    //找到尾节点连接的该单链表的某个节点
    LinkNode *node = locateElementByWx(L, wx);
    //找到尾节点(此处偷懒了 直接根据链表大小调用已经写好的locateElementByWx()方法找到尾节点指针)
    LinkNode *tailNode = locateElementByWx(L, LinkListNodeNum);
    //正式创造出了环，把尾节点的next域指向该单链表中任何一个节点
    tailNode->next = node;
}


void printLinkList(LinkNode *&linkNode) {
    LinkNode *p = linkNode->next;
    int i = 1;
    while (p != NULL) {
        cout << "该元素在线性表中的位序是(不含头节点):" << i << ",值是:" << p->data << endl;
        i++;
        p = p->next;
    }
}

/**
 * 计算线性表的长度（不含头节点）并返回
 * 计算长度不需要改变该线性表的元素值 所以不用加取地址符号
 * @param L
 * @return
 */
int listLength(LinkNode *L) {
    int num = 0;
    LinkNode *p = L->next;
    while (p != NULL) {
        num++;
        p = p->next;
    }
    cout << "该线性表的长度为(不含头节点):" << num << endl;
    return num;
}

bool isHaveElement(vector<LinkNode *> &v, LinkNode *p) {
    for (int i = 0; i < v.size(); i++) {
        if (p == v.at(i)) {
            return true;
        }
    }
    return false;
}


/**
 * 判断该单链表是否有环 有返回1  没有返回0
 *  判断方法:
 * @return
 */
int isHasCircle(LinkNode *&L, vector<LinkNode *> &v) {
    LinkNode *p = L;
    while (p != NULL) {
        bool currIsHaveIn = isHaveElement(v, p->next);
        if (currIsHaveIn) {
            return 1;
        } else {
            v.push_back(p->next);
            p = p->next;
        }
    }
    return 0;
}

/**
 * 销毁线性表(单链表的线性表)
 * @param L
 */
void destroy(LinkNode *&L) {
    cout << "即将销毁当前线性表,地址:" << L << endl;
    LinkNode *pre = L;
    LinkNode *p = L->next;
    while (p != NULL) {
        free(pre);
        pre = p;
        p = p->next;
    }
    cout.flush();
    cout << "当前线性表已经销毁!线性表地址:" << endl;
}

void checkIfDestory(LinkNode *&L) {
    LinkNode *p = L;
    while (p != NULL) {
        cout << "进入一次..." << endl;
        p = p->next;
    }

}

int main() {


    //声明一个单链表
    LinkNode *linkNode;

    //初始化该线性表、创建头节点、赋初试测试值
    vector<LinkNode *> v;
    initAndCreateListAndSetData(linkNode);
    //练习:计算并输出该线性表的长度(还没有环的状态下)
    listLength(linkNode);
    //练习:输出线性表所有元素元素值(还没有环的状态下)
    printLinkList(linkNode);
    createHuan(linkNode, HuanPos);
    //正式判断是否有环
    int result = isHasCircle(linkNode, v);
    cout << "该单链表中 " << (result == 1 ? "有环" : "没有环") << endl;
    cout.flush();
    //销毁线性表！
    destroy(linkNode);

    //检测该线性表是否已经销毁
    checkIfDestory(linkNode);
}

